package demo2;

import java.util.*;

public class Solution {

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k){
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();

        for(String s : strs){
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            String key = new String(ch);
            if(!hash.containsKey(key)){
                hash.put(key, new ArrayList<>());
            }
            hash.get(key).add(s);
        }
        return new ArrayList<>(hash.values());
    }

    public String longestCommonPrefix1(String[] strs) {
        for(int i = 0; i < strs[0].length(); i++){
            char ch = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++){
                if(i == strs[j].length() || strs[j].charAt(i) != ch){
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    public String longestCommonPrefix(String[] strs) {
        String tmp = strs[0];
        for(int i = 1; i < strs.length; i++){
            tmp = change(tmp, strs[i]);
        }
        return tmp;
    }
    public static String change(String s1, String s2){
        int i = 0;
        while(i < Math.min(s1.length(), s2.length()) && s1.charAt(i) == s2.charAt(i)) { i++;}
        return s1.substring(0, i);
    }

    public String longestPalindrome(String s) {
        int start = 0, len = 0;
        for(int i = 0; i < s.length(); i++){
            int left = i, right = i;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            if(right - left - 1 > len){
                start = left + 1;
                len = right - left - 1;
            }

            left = i;
            right = i + 1;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            if(right - left - 1 > len){
                start = left + 1;
                len = right - left - 1;
            }
        }
        return s.substring(start, start + len);
    }

    public static String addBinary(String a, String b) {
        StringBuffer buf = new StringBuffer();
        int s1 = a.length() - 1, s2 = b.length() - 1, t = 0;
        while(s1 >= 0 || s2 >= 0 || t != 0){
            if(s1 >= 0) { t += (a.charAt(s1--) - '0');}
            if(s2 >= 0) { t += (b.charAt(s2--) - '0');}
            buf.append(t % 2);
            t /= 2;
        }
        while(buf.length() > 1 && buf.charAt(buf.length() - 1) == '0'){
            buf.deleteCharAt(buf.length() - 1);
        }
        return buf.reverse().toString();
    }

    public String multiply(String num1, String num2) {
        int n = num1.length(), m = num2.length();
        char[] s1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] s2 = new StringBuffer(num2).reverse().toString().toCharArray();
        int[] num = new int[n + m - 1];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                num[i + j] += (s1[i] - '0') * (s2[j] - '0');
            }
        }

        StringBuffer buf = new StringBuffer();
        int index = 0, t = 0;
        while(index < n + m - 1 || t != 0){
            if(index < n + m - 1) { t += num[index++];}
            buf.append(t % 10);
            t /= 10;
        }

        while(buf.length() > 1 && buf.charAt(buf.length() - 1) == '0'){
            buf.deleteCharAt(buf.length() - 1);
        }
        return buf.reverse().toString();
    }

    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(!stack.isEmpty() && stack.peek() == s.charAt(i)){
                stack.pop();
            }else{
                stack.add(s.charAt(i));
            }
        }
        StringBuffer buf = new StringBuffer();
        while(!stack.isEmpty()){
            buf.append(stack.pop());
        }
        return buf.reverse().toString();
    }

    public String removeDuplicates2(String s) {
        StringBuffer buf = new StringBuffer();
        char[] ch = s.toCharArray();
        for(char x : ch){
            if(buf.length() > 0 && buf.charAt(buf.length() - 1) == x){
                buf.deleteCharAt(buf.length() - 1);
            }else{
                buf.append(x);
            }
        }
        return buf.toString();
    }

    public boolean backspaceCompare(String s, String t) {
        StringBuffer buf1 = new StringBuffer();
        StringBuffer buf2 = new StringBuffer();
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();

        for(int i = 0; i < ch1.length; i++){
            if(ch1[i] == '#'){
                if(buf1.length() > 0) { buf1.deleteCharAt(buf1.length() - 1);}
            }else{
                buf1.append(ch1[i]);
            }
        }
        for(int i = 0; i < ch2.length; i++){
            if(ch2[i] == '#'){
                if(buf2.length() > 0) { buf2.deleteCharAt(buf2.length() - 1);}
            }else{
                buf2.append(ch2[i]);
            }
        }
        return buf1.toString().equals(buf2.toString());
    }

    public int calculate(String s) {
        char[] ch = s.toCharArray();
        int i = 0, n = s.length();
        char op = '+';
        Stack<Integer> stack = new Stack<>();

        while(i < n){
            if(ch[i] == ' '){
                i++;
            }else if(ch[i] >= '0' && ch[i] <= '9'){
                int tmp = 0;
                while(i < n && ch[i] >= '0' && ch[i] <= '9'){
                    tmp = tmp * 10 + (ch[i] - '0');
                    i++;
                }
                if(op == '+'){
                    stack.add(tmp);
                }else if(op == '-'){
                    stack.add(- tmp);
                }else if(op == '*'){
                    stack.add(stack.pop() * tmp);
                }else{
                    stack.add(stack.pop() / tmp);
                }
            }else{
                op = ch[i++];
            }
        }

        int ret = 0;
        while(!stack.isEmpty()){
            ret += stack.pop();
        }
        return ret;
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> st = new Stack<>();
        int i = 0;
        for(int x : pushed){
            st.add(x);
            while(!st.isEmpty() && st.peek() == popped[i]){
                i++;
                st.pop();
            }
        }
        return st.isEmpty();
    }


    public static void main(String[] args) {
        System.out.println(addBinary("1010","1011"));
    }
}
